/* 
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

输入: [0,1,3]
输出: 2


思路1：找出与索引不等的项的索引就是缺失的数字
思路2：
排序数组中的搜索问题，首先想到二分法（双指针）
每次取中间的数看是否与索引相等，相等的话证明缺失的数在右数组，不等的话证明在左数组
*/
/**
 * @param {number[]} nums
 * @return {number}
 */
 var missingNumber = function(nums) {
    //  思路1
    /* const len =nums.length
    // 每一项与索引相等，找出不等的项的索引就是缺失的数字
    for(let i=0;i<len;i++){
        if(nums[i]!=i){
            return i
        }
    }
    // 如果遍历完没找到，缺失的就是len
    return len */

    // 思路2
    const len =nums.length
    let i=0,j=len-1
    while(i<=j){
        // 找出i与j之间的中间数
        let mid=Math.floor((i+j)/2)
        if(nums[mid]==mid){
            // 缺失的数在右数组
            i=mid+1
        }else{
            // 缺失的数在左数组
            j=mid-1
        }
    }
    return i

};

let nums = [0,2,3]

let res = missingNumber(nums)
console.log(res);